Úloha 1.
(10 bodů) Na vstupu je posloupnost n celých čísel. Určete celé číslo, které má ze všech celých čísel, které se ve vstupní posloupnosti nevyskytují, nejmenší absolutní hodnotu. Pokud existují dvě taková čísla, stačí vrátit libovolné z nich (ve vašem popisu řešení ale upřesněte, zdali v takovém případě vracíte číslo záporné či kladné).
Navrhněte postup, jak správně vyřešit úlohu s co nejlepší časovou a prostorovou složitostí (měřeno nejhorším případem) vzhledem k délce vstupní posloupnosti. Maximální počet bodů bude udělen jen za řešení s časovou i prostorovou složitostí O(n).
(a) Popište algoritmus (včetně datových struktur, které případně budete používat). Programový kód není povinný, slovní vysvětlení zvoleného postupu řešení naopak povinné je. Nepoužívejte prosím žádné netriviální datové struktury (typu zásobník, fronta, halda, slovník), jejichž algoritmus sami nepopíšete a neodvodíte jeho časovou složitost.
(b) Zdůvodněte správnost algoritmu.
(c) Odvoďte časovou a prostorovou složitost (v nejhorším případě).
**Příklad: **
vstup: 22 8 -5 0 -2000 2 1 20 100000 7 -15 20 -1
výstup: -2
Poznámka: Úlohu lze vyřešit s časovou i prostorovou složitostí O(n). Netriviální počet bodů bude ovšem udělen i za méně efektivní řešení.
Úloha 2.
**(10 bodů) **Je zadán binární strom o n vrcholech, v nichž jsou uložena navzájem různá celá čísla. Navrhněte efektivní algoritmus, který pro zadané číslo x vrátí seznam čísel všech vrcholů, které leží **na stejné hladině **jako vrchol s číslem x. Pokud hodnota x ve stromě není, bude vrácen prázdný seznam.
Hladinu binárního stromu tvoří všechny vrcholy se stejnou vzdáleností od kořene.
(a) Svoje řešení zapište jako funkci v Pythonu, využijte definici třídy pro vrchol binárního stromu i hlavičku funkce uvedené níže a váš kód prosím opatřete komentáři,
(b) zdůvodněte správnost,
(c) odvoďte časovou složitost (v nejhorším případě).
class VrcholBinStromu:
"""třída pro reprezentaci vrcholu binárního stromu"""
def __init__(self, info = None, levy = None, pravy = None):
self.info = info # data
self.levy = levy # levé dítě
self.pravy = pravy # pravé dítě
def hladina(koren : VrcholBinStromu, x : int):
"""
koren : kořen zadaného binárního stromu
x : zadané ohodnocení hledaného vrcholu
vrátí : seznam čísel vrcholů na hladině obsahující x
"""
Úloha 3.
Odpovězte na otázky.
(a) (5 bodů) Uvažte následující problém.
Vstup: Setříděné pole a délky n , hodnoty x,y takové, že x≤y
Výstup: (libovolný) index i takový, že x ≤ a[i] ≤ y
False pokud žádný takový neexistuje
Dokažte nebo vyvraťte následující tvrzení, svoji odpověď zdůvodněte:
Časová složitost řešení výše uvedeného problému porovnávacím algoritmem je Θ(log n).
Porovnávací algoritmus přistupuje k prvkům zadaným na vstupu prostřednictvím operace porovnání dvou prvků
p < q , p > q , p ≤ q , p ≥ q , p = q ,
hodnoty prvků jinak nevyužívá.
(b) (5 bodů) Jsou zadány dva aritmetické výrazy v různých notacích:
(b1) 1 2 - 3 + 4 5 - / 6 7 - * (b2) - 1 - * - 2 + * 3 4 5 6 7
Ke každému z výrazů
určete, o jakou notaci se jedná (infix, prefix, postfix),
sestrojte příslušný **strom aritmetického výrazu **
a vypište hodnoty (operátory i operandy) v něm uložené v pořadí, v němž budou navštíveny při **průchodu stromem do šířky **(děti každého vrcholu navštěvujeme v pořadí levé, pravé).
Ve vaší odpovědi stačí vypsat hodnoty v požadovaném pořadí, nemusíte uvádět strom ani zdůvodnění.